829. Consecutive Numbers Sum
Hard

Given a positive integer n, how many ways can we write it as a sum of consecutive positive integers?

Example 1:

Input: n = 5
Output: 2
Explanation: 5 = 5 = 2 + 3

Example 2:

Input: n = 9
Output: 3
Explanation: 9 = 9 = 4 + 5 = 2 + 3 + 4

Example 3:

Input: n = 15
Output: 4
Explanation: 15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5

Note: 1 <= n <= 10 ^ 9.

Accepted
48,035
Submissions
122,058
Seen this question in a real interview before?
Companies
Related Topics

Average Rating: 3.50 (62 votes)

Premium

Overview

Find Divisors / Integer Factorization Problem

NN is a sum of kk consecutive numbers, i.e. N=(x+1)+(x+2)+...+(x+k)N = (x + 1) + (x + 2) + ... + (x + k).

simple

Let's regroup the terms N=xk+(1+2+...+k)N = x k + (1 + 2 + ... + k) and use well-known formula for the sum of natural numbers 1+2+...+k=k(k+1)21 + 2 + ... + k = \frac{k(k + 1)}{2}:

N=xk+k(k+1)2(1) N = x k + \frac{k (k + 1)}{2} \qquad (1)

2N=k(2x+k+1)(2) 2N = k (2x + k + 1) \qquad (2)

That means, the problem is to figure out all possible pairs of kk and 2x+k+12x + k + 1 which are both divisors of a number 2N2N. To find a number of ways to factor 2N2N is the so-called Integer Factorisation problem.

The best way to solve this problem is to run Shor's Algorithm on the quantum computer, that requires O(log2NloglogNlogloglogN)\mathcal{O}(\log^2 N \log \log N \log \log \log N) time. If there is no quantum computer in the interview room, just use classical GNFS Algorithm, which runs in a decent O(elog1/3N(loglogN)2/3)\mathcal{O}(e^{\log^{1/3} N (\log \log N)^{2/3}}) time.

Speaking seriously, one has to stay reasonable during the interview and figure out the right balance between speed and simplicity.

Time Complexity to Target During the Interview: O(N)\mathcal{O}(\sqrt{N})

First, one could iterate from 11 to NN and figure out all divisors in a linear time.

simple

Second, the divisors are paired, i.e. if number ii is a divisor of NN, then number N/iN / i is a divisor of NN too. That means it's enough to iterate up to N\sqrt{N}.

simple

O(N)\mathcal{O}(\sqrt{N}) is definitely enough for the interview. In this article, we consider two simple solutions, which are good suite for the interview and keep the rest out of scope.


Approach 1: Mathematical: Sum of First kk Natural Numbers, O(N)\mathcal{O}(\sqrt{N}) time

Intuition

Let's use the formula we derived above

N=xk+k(k+1)2(1) N = x k + \frac{k (k + 1)}{2} \qquad (1)

derive xx

x=Nkk+12(3) x = \frac{N}{k} - \frac{k + 1}{2} \qquad (3)

and set two constraints:

  • xx should be greater or equal to zero.

  • xx should be an integer.

The first constraint is easy to apply using completing the square technique

Nkk+12(4) \frac{N}{k} \ge \frac{k + 1}{2} \qquad (4)

2N+14(k+12)2(5) 2N + \frac{1}{4} \ge \left(k + \frac{1}{2}\right)^2 \qquad (5)

k2N+1412(6) k \le \sqrt{2N + \frac{1}{4}} - \frac{1}{2} \qquad (6)

The first constraint sets the upper boundary for kk. The second constraint, xx should be an integer, can be verified during the iteration over kk.

Algorithm

  • Initiate the counter to zero.

  • Iterate over kk from 11 to 2N+1412\sqrt{2N + \frac{1}{4}} - \frac{1}{2}.

  • If x=Nkk+12x = \frac{N}{k} - \frac{k + 1}{2} is an integer, increase the counter by one.

  • Return the counter.

Implementation

Complexity Analysis

  • Time Complexity: O(N)\mathcal{O}(\sqrt{N}).

  • Space Complexity: O(1)O(1).


Approach 2: Mathematical: Decrease NN Gradually, O(N)\mathcal{O}(\sqrt{N}) time

Intuition

Now let's optimize Approach 1. The idea is to use the same iteration limits for kk, and to decrease NN by kk at each step.

simple

At each step, we check if NN can be composed by the sum of kk consecutive numbers, i.e. N=(x+1)+(x+2)+...+(x+k)=xk+(1+2+...+k)N = (x + 1) + (x + 2) + ... + (x + k) = xk + (1 + 2 + ... + k).

By removing all the complementary terms (1, 2, ... k) one by one, we reduce the number NN from xk+(1+2+...+k)xk + (1 + 2 + ... + k) down to N=xkN = x k. Since xx should be an integer, kk should be a divisor of NN, i.e. N % k == 0.

Algorithm

  • Initiate the counter to zero.

  • Iterate over kk from 11 to 2N+1412\sqrt{2N + \frac{1}{4}} - \frac{1}{2}.

  • Decrease NN by kk, to keep xkx k term only.

  • Verify that xx is an integer: N % k == 0. If it's the case, increase the counter by one.

  • Return the counter.

Implementation

Complexity Analysis

  • Time Complexity: O(N)\mathcal{O}(\sqrt{N}).

  • Space Complexity: O(1)O(1).


Report Article Issue

Comments: 32
mooning's avatar
Read More

If there is no quantum computer in the interview room....

201
Show 2 replies
Reply
Share
Report
ssged's avatar
Read More

If somebody asks you this in the interview, don't take that offer and also let people know on blind/reddit/leetcode forums etc so other people can also save their time from such stupid companies.

137
Show 4 replies
Reply
Share
Report
catamoose50's avatar
Read More

how many mathematicians does it take to write a web server? )

23
Reply
Share
Report
chaaloftin's avatar
Read More

The discussion section has way better answers than this. For anyone who came down to check the comments....don't bother with the solution.

22
Show 3 replies
Reply
Share
Report
carjam's avatar
Read More

A bit pedantic, "well-known formula for the sum of natural numbers." Solutions here all rely on the assumption that we know or can derive this.
Also 1+2+3+4+5+6 != 15 as stated

11
Show 2 replies
Reply
Share
Report
firefawkes's avatar
Read More

This is a very ProjectEuler type of question.

6
Reply
Share
Report
red_cheetah's avatar
Read More

Here's my simple understanding of the problem:
For representing N as sum of consecutive integers we have the following scenarios:

N = M + 0 (Base case when M == N, or when N is sum of only one number i.e itself)
N = M + (M + 1) (when N is sum of two consecutive numbers e.g 9 = 4+5, here M is 4 ) => 2M + 1
N = M + (M+1) + (M+2) (when N is sum of 3 consecutive numbers, e.g 9 = 2+3+4, here M is 2) => 3
M + 3
N = M + (M+1) + (M+2) + (M+3) => 4*M + 6
N = M + (M+1) + (M+2) + (M+3) + (M+4) => 5M + 10
N = M + (M+1) + (M+2) + (M+3) + (M+4) + (M + 5) => 6M + 15
....... and so on

so looking at this series we need to find the unique numbers of M such that they fit our equations. (M needs to be an integer)

So we can write it as something like this =>

class Solution:
    def consecutiveNumbersSum(self, N: int) -> int:
        
        constant_term = 0
        divisor = 1
        ans = 0
        while constant_term < N:
            if ((N-constant_term)/divisor).is_integer():
                ans += 1
            
            constant_term = constant_term + divisor
            divisor += 1
        
        return ans
        

we are looping till constant_term is less than N, because
1.) if the constant term becomes greater than N there'll be no solution furthermore.
2.) if the constant term gets equal to N then this case will be similar to the very first case.

3
Reply
Share
Report
waynelaizye's avatar
Read More

Found a solution that is to find the count of "odd factors". But don't ask me, I don't know why....

def consecutiveNumbersSum(self, N):
    count = 0
    for i in range(1, int(math.sqrt(N))+1):
        if N%i == 0:
            if i%2:
                count += 1
            if (N/i)%2 and N/i != i:
                count += 1
    return count

4
Show 1 reply
Reply
Share
Report
vrawal's avatar
Read More

Simple Solution : check if((f1 + f2)%2 == 1 && abs(f1 - f2)%2==1) for all factor pairs f1, f2

  • Tauqueer Ahmed, THE GREAT MATHEMATICIAN

2
Reply
Share
Report
GokulGC's avatar
Read More

Wowwwww ... This solution is amazing and simple

2
Reply
Share
Report

You don't have any submissions yet.

/23
Contribute
|||
Saved
Trie
This list is empty.